package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.ArrayUtils;

import java.util.ArrayList;
import java.util.List;

public class SpiralMatrix {

    int[][] direct = {
            {0, 1},
            {1, 0},
            {0, -1},
            {-1, 0},
    };

    /**
     * 顺时针遍历，如果下一格超过边界或者已经遍历过了，改变方向
     *
     * @param matrix m == matrix.length
     *               n == matrix[i].length
     *               1 <= m, n <= 10
     *               -100 <= matrix[i][j] <= 100
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int numSize = m * n;
        boolean[][] visit = new boolean[m][n];
        List<Integer> res = new ArrayList<>(numSize);
        int x = 0, y = 0, directIndex = 0;
        while (res.size() < numSize){
            res.add(matrix[x][y]);
            visit[x][y] = true;
            int[] d = direct[directIndex];
            x += d[0];
            y += d[1];
            if (x < 0 || x >= m || y < 0 || y >= n || visit[x][y]){
                directIndex++;
                if (directIndex == 4){
                    directIndex = 0;
                }
                x = x - d[0] + direct[directIndex][0];
                y = y - d[1]  + direct[directIndex][1];
            }
        }
        return res;
    }


    public static void main(String[] args) {
        int[][] matrix = ArrayUtils.parseArray("" +
                "[[1,2,3],[4,5,6],[7,8,9]]" +
                "", int[].class);
        List<Integer> integers = new SpiralMatrix().spiralOrder(matrix);
        System.out.println(integers);
    }
}
